/**
 * @version: V1.0
 * @Title: CustomHeap.java
 * @Description:
 * @author wangshipeng
 * @date 2022-01-12 22:15
 * @Copyright: 2022-01-12
 */

package com.peng.heap;

import java.util.*;

/**
 * @author wangshipeng
 * @ClassName: CustomHeap
 * @Description: 加强堆
 * @date 2022-01-12 22:15
 */
public class MyCustomEnhanceHeap<T> {

    private int heapSize;
    private List<T> heap;
    private Map<T, Integer> objIndexMap;
    private Comparator<T> comparator;

    public MyCustomEnhanceHeap(Comparator<T> comparator) {
        heapSize = 0;
        heap = new ArrayList<>();
        objIndexMap = new HashMap<>();
        this.comparator = comparator;
    }

    public static void main(String[] args) {
        MyCustomEnhanceHeap<Integer> heap = new MyCustomEnhanceHeap<>(Comparator.comparingInt(item -> item));
        heap.push(3);
        heap.push(5);
        heap.push(1);
        heap.push(9);
        heap.push(8);
        heap.push(2);
        heap.push(3);

        heap.remove(1);
        heap.remove(3);
        heap.printAllElements();

    }

    public void push(T obj) {
        heap.add(obj);
        objIndexMap.put(obj, heapSize);
        heapInsert(heapSize++);
    }

    public T pop() {
        T returnObj = heap.get(0);
        swap(0, heapSize - 1);
        objIndexMap.remove(returnObj);
        heap.remove(--heapSize);
        heapify(0);
        return returnObj;
    }

    public T peek() {
        return heap.get(0);
    }

    public void resign(T obj) {
        heapInsert(objIndexMap.get(obj));
        heapify(objIndexMap.get(obj));
    }

    public void remove(T obj) {
//        Integer deleteObjIndex = objIndexMap.get(obj);
//
//        T replaceObj = heap.get(heapSize - 1);
//
//        objIndexMap.remove(obj);
//        heap.remove(--heapSize);
//        if(replaceObj!=obj){
//            heap.set(deleteObjIndex,replaceObj);
//            objIndexMap.put(replaceObj,deleteObjIndex);
//            resign(replaceObj);
//        }


        Integer pos = objIndexMap.get(obj);
        T replaceObj = heap.get(heapSize - 1);
        heap.remove(--heapSize);
        objIndexMap.remove(obj);
        if (replaceObj != obj) {
            heap.set(pos, replaceObj);
            objIndexMap.put(replaceObj, pos);
            resign(replaceObj);
        }

    }

    public void printAllElements() {
        heap.forEach(System.out::println);
    }

    private void heapify(int index) {
        int left = (index << 1) + 1;
        while (left < heapSize) {
            int lowestPos = left + 1 < heapSize && comparator.compare(heap.get(left + 1), heap.get(left)) < 0 ? left + 1 : left;
            lowestPos = comparator.compare(heap.get(lowestPos), heap.get(index)) < 0 ? lowestPos : index;
            if (lowestPos == index) {
                break;
            }
            swap(lowestPos, index);
            index = lowestPos;
            left = (index << 1) + 1;
        }
    }

    private void heapInsert(int index) {
        while (comparator.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
            swap(index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    private void swap(int i, int j) {
        T obj1 = heap.get(i);
        T obj2 = heap.get(j);
        heap.set(i, obj2);
        heap.set(j, obj1);
        objIndexMap.put(obj1, j);
        objIndexMap.put(obj2, i);
    }


}
